package 左哥算法.ch01异或运算;

import org.junit.Test;

import java.util.List;

public class Ch01异或运算 {

    /**
     * 异或交换数
     *  异或可以实现交换的原理：
     *      1：因为0^x=x，x^x=0
     *      2：且异或运算符合交换律和结合率：即：x^y^z=x^z^y，x^y^z=x^(y^z)
     *      所以：下面这个式子可以看成：
     *          a=x,b=y;    //此时a和b的值
     *          a=x^y;      //a=x^y,b=y
     *          b=a^b;      //a=x^y,b=x^y^y=x^0=x
     *          a=a^b;      //a=x^y^x=y,b=x
     *  这种方式交换的是内存地址，所以必须保证交换的两个数内存地址是不同的(值可以一样)
     */
    @Test
    public void test1(){
        int a =10;
        int b =20;
        a=a^b;
        b=a^b;
        a=a^b;

        System.out.println(a);
        System.out.println(b);
    }

    /**
     * 给出一个整数数组，已知此数组只有一个数出现过奇数次
     * 请找出这个数
     * 0^n=n,n^n=0
     * a^b^c=a^c^b， (a^b)^c=a^(b^c)
     */
    @Test
    public void test02(){
        int[] arr = {1, 3, 3, 2, 4, 2, 3, 4, 1};
        int res=0;
        for (int i : arr) {
            res=res^i;
        }
        System.out.println(res);
    }

    /**
     *给出一个整数数组，已知此数组有两个数出现过奇数次
     * 请找出这两个数
     *思路：
     * 先用一个变量eor对数组所有元素异或一次，得到a^b
     * 而由于a!=b，即a^b!=0，即a^b一定会有一位二进制为1，这一位就是a和b不同的二进制位
     * 我们可以用这个不同的二进制位将原先的数组区分为两部分，由于a和b在这个二进制位上是不同的，所以a和b会在不同的部分
     * 这时候我们用变量res对其中一部分进行异或，就会得到a或b其中一个
     * 这时再用eor对res进行异或，即得到剩下的一个
     */
    @Test
    public void test03(){
        int[] arr = {1, 3, 3, 2, 4, 2, 3, 4, 1,6};
        List list=null;
        int eor=0;

        for (int i : arr) { //对数组所有元素进行异或得到 a^b
            eor=eor^i;
        }

        int rightOne=eor&(~eor+1);  //找到二进制位最右侧的1
        int res=0;
        for (int i : arr) {
            if ((i&rightOne)==0){
                res=res^i;
            }
        }
        System.out.println(res);
        System.out.println(res^eor);
    }

//    /**
//     *给出一个整数数组，请找出数组中所有出现过奇数次的数
//     *思路：
//     *  先用一个变量eor对数组所有元素异或一次，得到a^b^c^d^e
//     *
//     */
//    @Test
//    public void test04(){
//
//    }

}
